package com.yangzhe.algorithm.c022;

/**
 * 翻转对数量
 * 测试链接 : https://leetcode.cn/problems/reverse-pairs/
 */
class Code02_ReversePairs {

	public static void main(String[] args) {
		Code02_ReversePairs myReversePairs = new Code02_ReversePairs();
		int[] nums = {2147483647,2147483647,2147483647,2147483647,2147483647,2147483647};
		System.out.println(myReversePairs.reversePairs(nums));
	}

	private int[] help;

	public int reversePairs(int[] nums) {
		if (nums.length <= 1) {
			return 0;
		}
		help = new int[nums.length];

		return mergeSortAndCalcReversePairs(nums, 0, nums.length - 1);
	}

	public int mergeSortAndCalcReversePairs(int[] nums, int l, int r) {
		if (l == r) {
			return 0;
		}

		int m = (l + r) / 2;
		return mergeSortAndCalcReversePairs(nums, l, m) + mergeSortAndCalcReversePairs(nums, m + 1, r) + mergeLeftAndRightAndCalcReversePairs(nums, l, m, r);
	}

	/**
	 * 过程是O(2n)，省略常数项复杂度是O(n)
	 */
	public int mergeLeftAndRightAndCalcReversePairs(int[] nums, int l, int m, int r) {
		// 1. 计算翻转对 此过程是O(n)
		int preReversePairs = 0;
		int reversePairs = 0;
		int lIndex = l;
		int rIndex = m + 1;
		for (;lIndex <= m; lIndex++) {
			while (rIndex <= r && (long)nums[lIndex] > 2 * (long)nums[rIndex]) {
				rIndex++;
				preReversePairs++;
			}
			reversePairs +=	preReversePairs;
		}



		// 2. 归并 合并左右两边，此过程是O(n)
		lIndex = l;
		rIndex = m + 1;
		int hIndex = l;
		// 2.1 哪边小把哪边copy到help中
		while(lIndex <= m && rIndex <= r) {
			help[hIndex++] = nums[lIndex] < nums[rIndex] ? nums[lIndex++] : nums[rIndex++];
		}

		// 2.2 把左边剩余copy到help中
		while(lIndex <= m) {
			help[hIndex++] = nums[lIndex++];
		}

		// 2.3 把右边剩余copy到help中
		while(rIndex <= r) {
			help[hIndex++] = nums[rIndex++];
		}

		// 2.4 把help中有序的数据刷回原数组
		for (int i = l; i <= r; i++) {
			nums[i] = help[i];
		}

		return reversePairs;
	}


}